// m

// 给定一个二叉树的根节点root
// 要求判断是否是一个有效的二叉搜索树

// 解题思路：递归遍历
// 根据题意进行递归遍历即可，前序，中序，后续都可以
// 以前序遍历为例，先判断根节点的值是否在（min_v,max_v）之间
//    1. 如果不在则返回false
//    2. 如果在区间内，则继续递归检测左右子树是否满足，都满足才是一棵二叉搜索树
// 当递归遍历左子树的时候，要将上界max_v改为左子树的根节点的值，因为左子树上所有节点的值均小于根节点的值
// 当递归遍历右子树的时候，要将下界min_v改为右子树的节点的根节点值，因为右子树上所有节点的值均大于根节点

function isValidBST(root) {
    function preorderTraversal(root, min_v, max_v) {
        if (!root) {
            return true
        }
        if (root.val >= max_v || root.val <= min_v) {
            return false
        }
        return preorderTraversal(root.left, min_v, root.val) && preorderTraversal(root.right, root.val, max_v)
    }
    return preorderTraversal(root, -Infinity, Infinity)
}

const root = {
    val: 4,
    left: {
        val: 3,
        left: {
            val: 2,
        },
        right: {
            val: 3.5,
            left: {
                val: 3.1
            }
        },
    },
    right: {
        val: 6,
    },
};

console.log(isValidBST(root))